package datastructure.figure05;



import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 图操作
 * G(V,E):其中G表示图，V是顶点，E是边
 *
 * @Filename: FigureTest
 * @Author: czh
 * @Data:2023/1/3 11:45
 * 表示方法： 二维数组(邻接矩阵)和链表(邻接表)
 */
public class FigureTest {
    @Test
    public void test01() {
        AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix(8);
        String[] vertexs = {"A", "B", "C", "D", "E", "F", "G", "H"};
        // 添加顶点
        for (String vertex : vertexs) {
            adjacencyMatrix.insertVertex(vertex);
        }
        // 添加边
        adjacencyMatrix.insertEdge(0, 1, 2); // A-B
        adjacencyMatrix.insertEdge(0, 2, 2); //A-C
        adjacencyMatrix.insertEdge(1, 2, 3); //B-C
        adjacencyMatrix.insertEdge(1, 3, 4); //B-D
        adjacencyMatrix.insertEdge(1, 4, 4); //B-E
        adjacencyMatrix.insertEdge(3, 7, 1);//C-G
        adjacencyMatrix.insertEdge(4, 7, 1);
        adjacencyMatrix.insertEdge(2, 5, 1);
        adjacencyMatrix.insertEdge(2, 6, 1);
        adjacencyMatrix.insertEdge(5, 6, 1);
        adjacencyMatrix.display();
        adjacencyMatrix.dfs(new boolean[adjacencyMatrix.vertexList.size()], 2);
        System.out.println();
        // 全局深度优先搜索
        adjacencyMatrix.dfs();
    }
}

/**
 * 邻接矩阵
 * 表示图中顶点之间相邻关系的矩阵
 */
class AdjacencyMatrix {
    List<String> vertexList; // 存储顶点集合
    int[][] edges;  // 存储图对应的邻接矩阵
    int numOfEdges;  // 边的数量
    boolean[] isVisited;   // 记录某个节点是否被访问

    // 构造器
    public AdjacencyMatrix(int n) {
        this.edges = new int[n][n];
        this.vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

    /**
     * 添加节点
     *
     * @param vertex
     */
    public void insertVertex(String vertex) {
        this.vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     第一个顶点的下标
     * @param v2     第二个顶点的下标
     * @param weight 边的权重
     */
    public void insertEdge(int v1, int v2, int weight) {
        this.edges[v1][v2] = weight;
        this.edges[v2][v1] = weight;
        this.numOfEdges++;
    }

    /**
     * 根据下标获取节点i信息
     *
     * @param i 顶点
     * @return
     */
    public String getVertexByIndex(int i) {
        return this.vertexList.get(i);
    }

    /**
     * 获取v1和v2顶点边的权重
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        return this.edges[v1][v2];
    }

    /**
     * 获取第一个邻接顶点的下标
     *
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < this.vertexList.size(); i++) {
            if (this.edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接顶点的下标来获取下一个邻接顶点下标
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (this.edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 显示图对应的矩阵
     */
    public void display() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 深度优先遍历算法
     * 1）访问初始顶点v，并标记节点v为以访问
     * 2）查找顶点v的第一个邻接顶点w
     * 3）若w存在，则继续执行4，若w不存在，则回到1，将从v的下一个顶点继续
     * 4）若w未被访问，对w进行深度优先遍历递归（即把w当作另一个v，然后进行步骤123）
     * 5）查找顶点v的w邻接顶点的下一个邻接顶点，转到步骤3
     */
    public void dfs(boolean[] isVisited, int i) {
        // 首先输出第一个访问的顶点
        System.out.print(getVertexByIndex(i) + "->");
        // 将顶点i设置成以访问
        isVisited[i] = true;
        // 查询顶点i的第一个邻接顶点w
        int w = getFirstNeighbor(i);
        // 存在邻接顶点
        while (w != -1) {
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            // 如果w顶点被访问过
            w = getNextNeighbor(i, w);
        }
    }

    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        // 遍历所有顶点，进行dfs回溯
        for (int i = 0; i < vertexList.size(); i++) {
            if ((!isVisited[i])) {
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 广度优先遍历
     */
    public void bfs(boolean[] isVisited, int i) {
        int u; // 表示队列的头顶点对应的下标
        int w; // 邻接顶点w
        // 队列，记录顶点的访问顺序
        LinkedList queue = new LinkedList();
        // 访问顶点，输出顶点信息
        System.out.print(getVertexByIndex(i) + "->");
        isVisited[i] = true;
        // 将顶点加到队列
        queue.addLast(i);

        while (!queue.isEmpty()) {
            // 取出队列的顶点下标
            u = (Integer) queue.removeFirst();
            // 得到第一个邻接顶点的下标w
            w = getFirstNeighbor(u);
            while (w != -1) {
                // 是否访问
                if (!isVisited[w]) {
                    System.out.print(getVertexByIndex(w) + "->");
                    // 标记已经访问
                    isVisited[w] = true;
                    // 入队
                    queue.addLast(w);
                }
                // 已u为前驱点，找w后面的第一个邻接点
                w = getNextNeighbor(u, w);   // 体现广度优先
            }
        }
    }

    public void bfs() {
        isVisited = new boolean[this.vertexList.size()];
        for (int i = 0; i < this.vertexList.size(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }
}